#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstring>
#include "BinarySearchTree.h"

template <typename T> void BST_sort( std::vector<T> & data )
{
    BinarySearchTree<T> bst;
    for( const T & x : data )
        bst.insert( x );
    bst.flatten( data );
}

template <typename T> void Randomized_BST_sort( std::vector<T> & data )
{
    std::random_shuffle( data.begin(), data.end() );
    BinarySearchTree<T> bst;
    for( const T & x : data )
        bst.insert( x );
    bst.flatten( data );
}

bool isIncreasing( const std::vector<int> & arr )
{
    for( int i = 0; i < arr.size() - 1; i++ )
        if( arr[i] > arr[i+1] ) return false;
    return true;
}

void test_BST_sort( const std::vector<int> & input )
{
    std::cout << "---------------------------------test_BST_sort-----------------------------------" << std::endl;
    int _t = clock();
    std::cout << "Initializing..." << std::endl;
    std::vector<int> arr = input;
    std::cout << "Sorting..." << std::endl;
    BST_sort(arr);
    std::cout << "Finished. Time: " << (double) (clock() - _t) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
    std::cout << "Result: " << ( isIncreasing(arr) ? "Passed" : "Failed" ) << std::endl;
}

void test_Randomized_BST_sort( const std::vector<int> & input )
{
    srand( time(0) );
    std::cout << "----------------------------test_Randomized_BST_sort-----------------------------" << std::endl;
    int _t = clock();
    std::cout << "Initializing..." << std::endl;
    std::vector<int> arr = input;
    std::cout << "Sorting..." << std::endl;
    Randomized_BST_sort(arr);
    std::cout << "Finished. Time: " << (double) (clock() - _t) / CLOCKS_PER_SEC * 1000 << "ms" << std::endl;
    std::cout << "Result: " << ( isIncreasing(arr) ? "Passed" : "Failed" ) << std::endl;
}

int main( int argc, char * argv[] )
{
    int n;
    std::vector<int> input;
    srand(time(0));

    sscanf(argv[1], "%d", &n);
    if( argc == 3 )
    {
        if( std::string(argv[2]) == "-i" )
        {
            for( int i = 0; i < n; i++ )
                input.push_back(i);
        }
        else
        {
            std::cout << "Unrecognized command " << argv[2] << std::endl;
            return 1;
        }
    }
    else
    {
        for( int i = 0; i < n; i++ )
            input.push_back(rand());
    }

    test_BST_sort( input );
    test_Randomized_BST_sort( input );

    return 0;
}